用队列实现杨辉三角

2023-12-24 11:22| 来源: 网络整理| 查看: 265

打印杨辉三角是一个经典问题，也是小白非常头疼的一个问题，其实掌握好诀窍也并不难，杨辉三角第一二行不用做什么处理，到了第三行及以后才需要处理，最简单的实现方式就是先找到规律，即首尾元素为1，中间元素是该位置上一行同列的元素及其前一个元素和(第三行开始，不包括首尾元素)，用二维数组实现是最简便便捷的方法此处不仅给出了杨辉三角的普通实现方式，也给出了杨辉三角的队列实现(PS:队列是一种数据结构，第二张实现方式需要有数据结构基础才能理解)

#include #define MAX 100 #include int main() { int arr[MAX][MAX] = { 0 }; int a = 0; int i = 0; int j = 0; printf("输入杨辉三角的范围："); scanf("%d", &a); for (i = 0; i if (j == 0) { arr[i][j] = 1; printf("%5d ", arr[i][j]); if (i == 0) { printf("\n"); } } if ((i == j) && (i!=0)) { arr[i][j] = 1; printf("%5d\n", arr[i][j]); } if ((j != 0) && (i != j)) { arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; printf("%5d ", arr[i][j]); } } } system("pause"); return 0; }

看完了杨辉三角的朴素实现方式，接下来简析队列实现方式，杨辉三角的行列数最大值相同，每一行比上一行多一个元素，有一定规律，这就为二维的存储结构转变为一维的结构提供可能性，以下为具体的实现过程：

#include #include //malloc函数需要用到该头文件 #define MAXQSIZE 200 //此程序用到循环队列 typedef int QElemType; typedef struct { QElemType *next; //int 类型指针 *base int front; //队头指针 int rear; //队尾指针 }SqQueue; // 结构体名称为SqQueue 包含三个子元素 void InitQueue(SqQueue *Q){ //构造一个空队列Q Q->next=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); //创建足够大的循环队列 if(!Q->next) exit(1); //若初始化队列不为空则退出 Q->front=Q->rear=0; //队列初始化条件 } void EnQueue(SqQueue *Q,QElemType e){ //插入的元素e为Q的新的队尾元素 if((Q->rear+1)%MAXQSIZE ==Q->front) exit(1); //判满满则退出 Q->next[Q->rear]=e; Q->rear=(Q->rear+1)%MAXQSIZE; //关键代码 } void DeQueue(SqQueue *Q){ //若队列不空，则删除Q的队头元素，用e返回其值 if(Q->front==Q->rear) exit(1); QElemType e = Q->next[Q->front]; Q->front=(Q->front+1)%MAXQSIZE; } QElemType GetHead(SqQueue *Q){ //返回队头元素 return Q->next[Q->front]; } int main(){ int N,n,c; QElemType t,x; //t,x用于存储第三行及以后计算产生的临时值 SqQueue f,*Q; Q=&f; InitQueue(Q); printf("请输入杨辉三角规模N:"); scanf("%d",&N); EnQueue(Q,1); //第一行的1 for(n=2;n t=GetHead(Q); //c从1号位开始逐一获取节点 DeQueue(Q); //获取完节点后队头指针往后移1 printf("%4d",t); //输出当前节点值 t用于存储当前节点值 x=GetHead(Q); //x用于获取下一个节点的节点值（前一个元素已出队用t保存） t=t+x; //计算两值之和 EnQueue(Q,t); //更新后的t值入队 } EnQueue(Q,1); //插入每一行最后一个元素1 printf("%4d",GetHead(Q)); DeQueue(Q); printf("\n"); //打印完当前行的上一行需要换行 } while(Q->front!=Q->rear){ //打印剩下未出队的元素(最后一行元素) printf("%4d",GetHead(Q)); DeQueue(Q); } return 0; }

在这里插入图片描述最后再附上一种只用一维实现的方式：

#include int main(){ long i,j,n,k; printf("请输入杨辉三角行数："); scanf("%ld",&n); for( i= 1;i printf("%ld\t",k); k=k*(i - j)/j; } printf("1\n");//这个用于打印每行最后一列的1 } return 0; }

【本文地址】

公司简介

联系我们